<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <!-- 矩阵中的路径 -->
    <script>
      // dfs 遍历四个方向，越界，不等提前返回，
      const exist = function (board, word) {
        const [m, n] = [board.length, board[0].length]
        // i --> 横，j --> 竖， index --> word 的第几个字符
        const dfs = (i, j, index) => {
          if (i >= m || i < 0 || j >= n || j < 0 || board[i][j] !== word[index]) return false
          // 如果 word 遍历结束，说明能满足题意
          if (index === word.length - 1) return true
          // 走到这里，说明找到了该字符，标记一下
          board[i][j] = ''
          // 继续递归四个方向
          let res = dfs(i - 1, j, index + 1) || dfs(i + 1, j, index + 1) || dfs(i, j + 1, index + 1) || dfs(i, j - 1, index + 1)
          // 恢复 矩阵
          board[i][j] = word[index]
          return res
        }
        // 矩阵的每个位置都可以是遍历的起点
        for (let i = 0; i < m; i++) {
          for (let j = 0; j < n; j++) {
            if (dfs(i, j, 0)) return true
          }
        }
        return false
      }
      console.log(
        exist(
          [
            ['a', 'b'],
            ['c', 'd']
          ],
          'abcd'
        )
      )
    </script>
  </body>
</html>
